VC Dimesion(Vapnik-Chervonenkis Dimension)

이산 hypothesis space $H$ 에 의해 Shattering될 수 있는 가장 가능한 큰 크기의 $J$ 의 subset $S$ 의 크기.
즉, hypothesis space가 target concept를 표현 가능한 가능성 혹은 수용 정도를 나타낸다.

Example

$J = {x ∣ x \in R}$
$H = {g ∣ g (x ∣ a, b) = {10 if (a \leq x \leq b) otherwise, a \in R, b \in R}$

위 상황에 대해서, VC dimension은 2라고 할 수 있다.
만약 $S = {x_{1}, x_{2}, x_{3}}$ 이라면, $x_{1} = 1, x_{2} = 0, x_{3} = 1$ 인 경우에 대해 Shattering 불가능한 상황이 된다. 이러한 경우에 대해, 최대 가능한 크기인 2가 VC dimension이 된다.

곧, 이는 Hypothesis space의 복잡함과 관련된다.

Triple Trade-off

아래의 3가지는, trade-off의 관계에 있다.

Capacity of hypothesis space $H$ : 상승함에 따라 bias는 낮아지지만, variance가 높아진다. 즉, $E$ 가 높아진다고 볼 수 있다.
Training set size $N$ : $E$ 가 낮아지지만, instance space $J$ 를 cover하는 정도가 커지게 된다.
Generalization Error $E$